#include <stdio.h>
#include <stdlib.h>
#include "test.h"

void counting_sort(int A[], int n) {
    if (n <= 0) return;
    int min = A[0], max = A[0];
    // 找出最小值和最大值
    for (int i = 1; i < n; i++) {
        if (A[i] < min) min = A[i];
        if (A[i] > max) max = A[i];
    }
    int range = max - min + 1;                                          //如果范围很大不合适。会爆炸溢
    int *count = (int *)calloc(range, sizeof(int)); // 计数数组
    int *output = (int *)malloc(n * sizeof(int));  // 输出数组

    // 统计元素出现次数
    for (int i = 0; i < n; i++)
        count[A[i] - min]++;

    // 累加计数数组
    for (int i = 1; i < range; i++)
        count[i] += count[i - 1];

    // 反向填充输出数组（确保稳定性）
    for (int i = n - 1; i >= 0; i--) {
        output[count[A[i] - min] - 1] = A[i];
        count[A[i] - min]--;
    }

    // 复制回原数组
    for (int i = 0; i < n; i++)
        A[i] = output[i];
    free(count);
    free(output);
}

int main() {
    int arr[] = {4, 2, 2, 8, 3, 3, 1}; // 示例数组
    int n = sizeof(arr) / sizeof(arr[0]);
    counting_sort(arr, n);
    printf("排序结果: ");
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]); // 输出: 1 2 2 3 3 4 8

        printf("\n");
        benchmark(counting_sort);
    return 0;
}


